package com.dragon.datastructure.queue;

/**
 * 用数组模拟队列
 * front: 代表队列队首元素的前一个索引
 * rear: 代表队列队尾元素的索引
 * <p>
 * 思路分析:
 * 1.队列为空   front == rear
 * 2.队列已满   rear == elementData.length - 1
 * 3.入队      rear往后面移动
 * 4.出队      front往后面移动
 * <p>
 * 问题分析以及优化:
 * 目前的队列只能使用一次，没有达到复用的效果
 *
 * @author dragon
 * @since 2019/12/17
 */
public class ArrayQueue {

    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 指向队列队首的前一个位置
     */
    private int front;

    /**
     * 指向队列队尾数据的角标
     */
    private int rear;

    /**
     * 真正存储元素的数组
     */
    private int[] elementData;


    public ArrayQueue(int initSize) {
        if (initSize <= 0) {
            throw new RuntimeException("队列初始化失败，队列长度不能小于或等于0");
        }
        elementData = new int[initSize];
        front = rear = -1;
    }

    public ArrayQueue() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 入队，添加元素，调整rear的角标
     */
    public void enqueue(int element) {
        if (isFull()) {
            throw new RuntimeException("队列已满");
        }
        elementData[++rear] = element;
    }

    /**
     * 出队列，将队首的元素pop出去，调整front的角标
     */
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }

        return elementData[++front];
    }

    /**
     * 看元素
     */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }

        return elementData[front + 1];
    }

    /**
     * 队列是否为空,当队尾 == 队首时，代表队列为空
     */
    public boolean isEmpty() {

        return rear == front;
    }

    /**
     * 队列是否已经满了，当队尾索引 == elementData.length - 1
     */
    public boolean isFull() {

        return rear == (elementData.length - 1);
    }

    /**
     * 队列的长度大小
     */
    public int size() {

        return rear - front;
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "ArrayQueue{}";
        }
        StringBuilder sb = new StringBuilder();
        sb.append("front->");
        for (int i = (front + 1); i < rear; i++) {
            sb.append(elementData[i] + "=>");
        }
        sb.append(elementData[rear] + "rear");

        return sb.toString();
    }
}
